/**
 * 找倒数第k个节点，然后返回值
 */

class Node{
public:
    int data;
    Node* next;
};

/// @brief 最快也要n
/// @param hair 带有头节点的 
/// @param k 倒数第k个
auto getLastK(Node* hair,int k){
    auto right=hair;
    auto left=hair;
    //先让right移动k个位置
    while (k--)
    {
        right=right->next;
    }
    //然后left和right一起移动
    while (right!=nullptr)
    {
        left=left->next;
        right=right->next;
    }
    return left;
}
#include<vector>
#include<iostream>
using namespace std;
auto initList(vector<int> v){
    auto hair=new Node();
    hair->data=0;
    hair->next=nullptr;
    auto tail=hair;

    for(auto var : v){
        auto temp=new Node();
        temp->data=var;
        temp->next=nullptr;
        tail->next=temp;
        tail=tail->next;
    }
    return hair;
}
int main(int argc,char* argv[]){
    
    vector<int> v={1,2,3,4,5,6,7,8,9};
    auto hair=initList(v);

    auto res=getLastK(hair,2);
    cout<<res->data<<endl;
    return 0;

    
}